﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0155_MyHashMap : IAlgorithm
    {
        // 706. 设计哈希映射

        // 不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
        // 实现 MyHashMap 类：
        //  MyHashMap() 用空映射初始化对象
        //  void put(int key, int value) 向 HashMap 插入一个键值对(key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
        //  int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
        //  void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

        // 提示：
        //  0 <= key, value <= 10^6
        //  最多调用 10^4 次 put、get 和 remove 方法

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public class MyHashMap
        {
            List<int[]> lst;

            private int[] GetEleFromLst(int key)
            {
                return lst.FirstOrDefault(x => x[0] == key);
            }

            public MyHashMap()
            {
                lst = new List<int[]>();
            }

            public void Put(int key, int value)
            {
                var ele = GetEleFromLst(key);
                if (ele != null)
                    ele[1] = value;
                else
                    lst.Add(new int[] { key, value });
            }

            public int Get(int key)
            {
                var ele = GetEleFromLst(key);
                if (ele != null)
                    return ele[1];
                else
                    return -1;
            }

            public void Remove(int key)
            {
                var ele = GetEleFromLst(key);
                if (ele != null)
                    lst.Remove(ele);
            }
        }

        public class MyHashMap1
        {

            public class Pair
            {
                private int key;
                private int value;

                public Pair(int key, int value)
                {
                    this.key = key;
                    this.value = value;
                }

                public int GetKey()
                {
                    return key;
                }

                public int GetValue()
                {
                    return value;
                }

                public void SetValue(int value)
                {
                    this.value = value;
                }
            }

            private const int BASE = 769;
            private LinkedList<Pair>[] data;

            public MyHashMap1()
            {
                data = new LinkedList<Pair>[BASE];
                for (int i = 0; i < BASE; ++i)
                {
                    data[i] = new LinkedList<Pair>();
                }
            }
            private static int Hash(int key)
            {
                return key % BASE;
            }

            public void Put(int key, int value)
            {
                int h = Hash(key);
                var linkedList = data[h];
                foreach (var pair in linkedList)
                    if (pair.GetKey() == key)
                    {
                        pair.SetValue(value);
                        return;
                    }
                data[h].AddLast(new Pair(key, value));
            }

            public int Get(int key)
            {
                int h = Hash(key);
                var linkedList = data[h];
                foreach (var pair in linkedList)
                    if (pair.GetKey() == key)
                        return pair.GetValue();
                return -1;
            }

            public void Remove(int key)
            {
                int h = Hash(key);
                var linkedList = data[h];
                foreach (var pair in linkedList)
                    if (pair.GetKey() == key)
                    {
                        linkedList.Remove(pair);
                        return;
                    }
            }
        }
    }
}
